درسنامه آموزشی فصل دوم ریاضیات گسسته کلاس دوازدهم ریاضی
درس 2: مدلسازی با گراف
برخی از مسائل روزمرهٔ زندگی را میتوان بهکمک مدلسازی نخست به یک مسئلهٔ ریاضی تبدیل نمود و سپس با حل مسئله ریاضی، مسئلهٔ اصلی را نیز حل کرد. بهطور کلی، بعضی مفاهیم ریاضی در مدلسازی مسائل زندگی واقعی بسیار پرکاربرد هستند. «احاطهگری» یکی از این مفاهیم پرکاربرد است که در ادامه با تاریخچه، مفهوم و کاربردهایی از آن آشنا خواهیم شد.
تاریخچه
در قرن نوزدهم میلادی مسائلی مانند «یافتن حداقل تعداد مهرهٔ وزیری که میتوانند با چینش مناسب تمام صفحهٔ شطرنج را بپوشانند» (یعنی هر خانهٔ صفحهٔ شطرنج که در آن وزیر قرار نگرفته است توسط حداقل یک وزیر تهدید شده باشند) ذهن برخی از مردم اروپا را به خود مشغول کرده بود.
تفکر دربارهٔ پرسشهایی از این دست باعث بهوجود آمدن مفهومی در شاخهٔ گراف در ریاضیات با نام احاطهگری شد. برای آشنایی با این مفهوم به مسئلهٔ بعد دقت کنید.
شکل زیر نقشهٔ منطقهای از یک شهر است. قرار است در برخی تقاطعهای این شهر دستگاههای خودپرداز بهگونهای نصب شود که دو شرط زیر را داشته باشد:
1- برای راحتی شهروندان دستگاهها بهگونهای نصب شده باشند که هر فرد در هر تقاطعی که قرار گرفته باشد، یا در همان تقاطع به دستگاه خودپرداز دسترسی داشته باشد و یا حداکثر با رفتن به یک تقاطع مجاور به دستگاه خودپرداز دسترسی پیدا کند.
2- به جهت صرفهجویی در هزینهها با کمترین تعداد دستگاه خودپرداز ممکن این کار صورت بگیرد.
حال فرض کنید منطقهٔ مورد نظر را با گراف شکل 2 مدلسازی کرده باشیم.
الف) در این مدلسازی تقاطعها و خیابانهای بین آنها هر کدام به چه صورت نمایش داده شدهاند؟
ب) رأسهایی از گراف را مشخص کنید که، با توجه به مدلسازی انجام شده، اگر خودپردازها در آن تقاطعها قرار گیرند، شرط 1 برآورده گردد. چنین مجموعهای از رئوس را یک مجموعهٔ احاطهگر برای گراف مینامیم. بهطور مثال مجموعهٔ شامل همه رئوس گراف G، یک مجموعه احاطهگر است. آیا میتوانید یک مجموعهٔ احاطهگر 4 عضوی مثال بزنید؟
معمولاً بهسادگی میتوان مجموعههای مختلفی از رئوس گراف G را مشخص کرد که در شرط 1 صدق کنند؛ بهعبارتی یک گراف میتواند مجموعههای احاطهگر گوناگونی داشته باشد. از طرفی واضح است که هر مجموعه که شامل یک مجموعهٔ احاطهگر باشد، احاطهگر است. در بین تمام مجموعههای احاطهگر یک گراف، مجموعهای را که کمترین تعداد عضو را داشته باشد مجموعۀ احاطهگر مینیمم آن گراف مینامیم. اگر چنین مجموعهای را برای گراف G بیابیم، این مجموعه در هر دو شرط 1 و 2 مطرح شده در مسئلهٔ بالا صدق خواهد کرد.
گاهی اوقات برای راحتی به یک مجموعهٔ احاطهگر مینیمم از گراف G، یک $-\gamma $ مجموعه میگوییم.
مثال: برای گراف شکل 3 که دور ${{C}_{7}}$ است، مجموعهٔ $\left\{ {{v}_{1}},{{v}_{3}},{{v}_{5}},{{v}_{7}} \right\}$ یک مجموعهٔ احاطهگر و مجموعههای $\left\{ {{v}_{1}},{{v}_{4}},{{v}_{7}} \right\}$ و $\left\{ {{v}_{1}},{{v}_{2}},{{v}_{5}} \right\}$ دو مجموعهٔ احاطهگر مینیمم یا اصطلاحاً دو $-\gamma $ مجموعهاند؛ و داریم $\gamma (G)=3$
مثال: فرض کنید j ،i ،h ،g ،f ،e ،d ،c ،b ،a و k شهرهای یک استان باشند و فاصلههای مستقیم این شهرها از یکدیگر، دوبهدو، مطابق جدول زیر باشد.
میخواهیم تعدادی ایستگاه رادیویی در برخی از شهرهای این استان تأسیس کنیم بهطوریکه همهٔ شهرهای استان از پوشش امواج رادیویی برخوردار گردند. و از طرفی برای کاهش هزینهها میخواهیم کمترین تعداد ممکن ایستگاه رادیویی را احداث کنیم. اگر هر ایستگاه رادیویی تا 50 کیلومتر اطراف خود را پوشش دهد، حداقل چند ایستگاه رادیویی احتیاج داریم و در چه شهرهایی باید آنها را احداث کنیم؟
حل: برای مدلسازی این مسئله کافی است گراف مربوط به آنرا به این طریق رسم کنیم که بهجای هر شهر یک رأس قرار دهیم و سپس دو رأس را به هم وصل کنیم اگر و تنها اگر فاصلهٔ مستقیم آن دو شهر از 50 کیلومتر بیشتر نباشد. در اینصورت مجموعهٔ احاطهگِر مینیمم برای گراف مذکور، جواب مسئله را مشخص میکند. (چرا؟)
با توجه به آنچه گفته شد گرافِ زیر، گرافِ حاصل از مدلسازی برای این مسئله است.
حال کافی است یک مجموعهٔ احاطهگر مینیمم در این گراف بیابیم و ایستگاههای رادیویی را در شهرهای متناظر با رئوس این مجموعه احاطهگِر مینیمم مستقر کنیم. یافتن یک مجموعهٔ احاطهگر مینیمم برای گراف فوق در تمرینات پایان درس به شما واگذار شده است.
کار در کلاس (صفحهٔ 46 کتاب درسی)
1- مشخص کنید کدامیک از مجموعههای زیر برای گراف شکل 5 احاطهگر هست و کدام نیست؟
$A=\left\{ a,b,c,d,e \right\}$ (الف
$B=\left\{ f,g,h,i,j \right\}$ (ب
$C=\left\{ a,b,j,h,g \right\}$ (پ
$D=\left\{ a,i,h \right\}$ (ت
$E=\left\{ f,g,h,e,d \right\}$ (ث
$F=\left\{ f,g,h,e \right\}$ (ج
$H=\left\{ g,h,e \right\}$ (چ
2- از مجموعههای مطرح شده در سؤال 1 که احاطهگر بودند در کدامیک از آنها رأس یا رأسهایی وجود دارد که با حذف آنها مجموعهٔ باقیمانده هنوز احاطهگر باشد؟
3- مجموعهای احاطهگر با کمترین تعداد رأس که میتوانید، بنویسید و پاسخ خود را با پاسخ همکلاسیهای خود مقایسه کنید.
4- یک مجموعهٔ احاطهگر مینیمال مشخص کنید که مینیمم نباشد.
5- آیا میتوان هر مجموعهٔ احاطهگر دلخواه غیر مینیمال را با حذف برخی رئوسش به یک مجموعهٔ احاطهگر مینیمال تبدیل کرد؟ (استدلال کنید)
مثال: در گراف شکل 6 یک مجموعهٔ احاطهگر غیر مینیمال انتخاب کنید و با حذف برخی رأسها، آنرا به یک مجموعهٔ احاطهگر مینیمال تبدیل نمایید.
حل: مجموعه $\left\{ a,b,c,d,e,f \right\}$ یک مجموعهٔ احاطهگر است. از آنجا که با حذف برخی رأسهای آن (مثلاً رأس a) این مجموعه باز هم احاطهگر خواهد بود، لذا احاطهگر مینیمال نیست.
حال با حذف سه رأس c، a و e از آن، مجموعهٔ $\left\{ b,d,f \right\}$ حاصل میشود که باز هم احاطهگر است اما چون این مجموعه با حذف هر یک از رأسهایش دیگر احاطهگر نخواهد بود لذا احاطهگر مینیمال است.
کار در کلاس (صفحهٔ 47 تا 48 کتاب درسی)
در گراف شکل 7:
1- مجموعهای از رئوس را مشخص نمایید که احاطهگر باشد.
2- مجموعهای از رئوس را مشخص نمایید که احاطهگر مینیمال باشد.
3- یک مجموعهٔ احاطهگر 3 عضوی مشخص نمایید.
4- آیا رأسی در گراف G وجود دارد که دو رأس از 3 رأس e، b و g را احاطه کند؟
5- حداقل تعداد رأسهایی که تمام رئوس گراف را احاطه میکنند چندتاست؟ ($\gamma (G)$ چند است؟)
معرفی یک نماد
با مفهوم جزء صحیح یک عدد آشنا هستید و میدانید که اگر x یک عدد صحیح باشد، $\left[ x \right]$ برابر با خود x است، و اگر عدد صحیح نباشد، عدد صحیح قبل از x است.
حال فرض کنید تعدادی از کارمندان یک شرکت قرار است با چند تاکسی به محلی بروند و هر 4 نفر یک تاکسی نیاز دارند.
الف) اگر تعداد کارمندان 12 نفر باشد، چند تاکسی نیاز است؟
ب) اگر تعداد کارمندان 14 نفر باشد چند تاکسی نیاز است؟
پ) اگر تعداد کارمندان 16 نفر باشد چند تاکسی نیاز است؟
ت) آیا با تقسیم تعداد کارمندان به عدد 4، تعداد تاکسیهای مورد نیاز بهدست میآید؟ اگر عدد حاصل عدد صحیح نباشد چه تعداد تاکسی نیاز است؟
ث) مفهوم سقف یک عدد که در ادامه مطرح شده است را میتوان در مواردی مشابه آنچه در اینجا مطرح شد بهکار برد.
در صورتیکه x عددی غیر صحیح باشد برای نمایش عدد صحیحِ بعد از x از $\left\lceil x \right\rceil $ استفاده میکنیم و آنرا سقف x میخوانیم. در حالت کلی
بنابراین:
$\begin{align}
& \left\lceil 3 \right\rceil =3\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left[ 3/5 \right]=3 \\
& \left\lceil 3 \right\rceil =3\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left[ 3/5 \right]=4 \\
\end{align}$
سؤال: برای کدام اعداد کف و سقف آنها با هم برابر است؟
فعالیت (صفحهٔ 48 کتاب درسی)
میدانیم در هر گراف، هر رأس خودش و تمام رئوس مجاورش را احاطه میکند.
1- در گراف زیر $\Delta $ چند است؟
2- هر رأس حداکثر چند رأس را احاطه میکند و این تعداد چه ارتباطی با $\Delta $ دارد؟
3- آیا 2 رأس میتوانند همهٔ رئوس گراف G را احاطه کنند؟
4- حداقل $\left\lceil \frac{10}{4} \right\rceil $ رأس برای احاطهٔ همهٔ رئوس لازم است. چرا؟
5- $\gamma (G)$ چند است؟
6- در یک گراف دلخواه با ماکزیمم درجهٔ $\Delta $، یک رأس دلخواه حداکثر چند رأس را احاطه میکند؟
7- تعداد کمتر از $\left\lceil \frac{n}{\Delta +1} \right\rceil $ رأس نمیتوانند تمام n رأس یک گراف را احاطه کنند. چرا؟
بنابراین:
کار در کلاس (صفحهٔ 49 کتاب درسی)
1- یک شبکه رایانهای متشکل از 16 کامپیوتر را در نظر بگیرید که در آن هر کامپیوتر، مطابق شکل 9 به چند کامپیوتر دیگر متصل است. گراف شکل 9 یک مدلسازی از شبکه مورد نظر است که در آن هر رأس نمایشگر یک کامپیوتر است و یال بین دو رأس نمایانگر آن است که کامپیوترهای نظیر به آن دو رأس مستقیماً با هم در ارتباطاند. میخواهیم مجموعهای با کمترین تعداد ممکن از کامپیوترها (رأسها) انتخاب کنیم. بهطوریکه توسط این مجموعه از کامپیوترها به تمام کامپیوترهای این شبکه وصل باشیم. مجموعهٔ انتخاب شده از رئوس برای گراف مورد نظر چه نوع مجموعهای است؟
2- با توجه به رابطهٔ $\left\lceil \frac{n}{\Delta +1} \right\rceil \le \gamma (G)$، حداقل چند رأس برای احاطه کردن تمام رئوس این گراف لازم است؟ آیا میتوانید مجموعهای احاطهگر با این تعداد رأس مشخص نمایید؟
3- گرافهای ${{P}_{10}}$، ${{P}_{9}}$، ${{C}_{10}}$ و ${{C}_{9}}$ را رسم کنید و عدد احاطهگری هر یک را مشخص نمایید.
4- گرافی مشخص کنید که بر آن عدد احاطهگر برابر $\left\lceil \frac{n}{\Delta +1} \right\rceil $ باشد.
5- گرافی مشخص کنید که بر آن عدد احاطهگر برابر $\left\lceil \frac{n}{\Delta +1} \right\rceil $ نباشد.
مثال: عدد احاطهگری گراف شکل 10 را مشخص و ادعای خود را ثابت کنید.
حل: به سادگی میتوان دید که مجموعهٔ دو عضوی $\left\{ a,c \right\}$ یک مجموعه احاطهگر است.
بنابراین عدد احاطهگری این گراف کوچکتر یا مساوی 2 است؛ یعنی $\gamma (G)\le 2$.
اما اگر $\gamma (G)=1$، یعنی یک رأس در گراف G وجود دارد که بهتنهایی تمام رئوس دیگر را احاطه کرده است (به تمام رئوس دیگر وصل است) یعنی رأسی با درجهٔ 4 در گراف وجود دارد که با توجه به گراف G میبینیم که چنین رأسی وجود ندارد و لذا $\gamma (G)\gt 1$. بنابراین $1\lt \gamma (G)\le 2$ و لذا $\gamma (G)=2$.
روش دیگر برای حل: نوع دیگری از استدلال به این صورت است که با توجه به کران پایین مطرح شده برای $\gamma (G)$ و اینکه $\Delta (G)=3$ داریم:
$\left\lceil \frac{n}{\Delta +1} \right\rceil \le \gamma (G)\Rightarrow \left\lceil \frac{5}{4} \right\rceil \le \gamma (G)$
بنابراین $2\le \gamma (G)$ و با توجه به مجموعهٔ احاطهگر دو عضوی ارائه شده در بالا داریم $\gamma (G)\le 2$ و لذا $\gamma (G)=2$.
کار در کلاس (صفحهٔ 50 کتاب درسی)
1- تمام $-\gamma $ مجموعههای (مجموعههای احاطهگر مینیمم) گراف G در مثال قبل را بنویسید.
2- عدد احاطهگری را برای هر یک از گرافهای زیر مشخص کنید.
فعالیت (صفحهٔ 50 کتاب درسی)
1- میخواهیم عدد احاطهگری گراف شکل 12 را مشخص کنیم.
الف) ابتدا میبینیم که با توجه به کران پایین $\left\lceil \frac{n}{\Delta +1} \right\rceil $ برای $\gamma (G)$ حداقل $\left\lceil \frac{8}{4} \right\rceil =2$ رأس برای احاطه کردن رئوس لازم است اما در مراحل بعدی که 2 رأس برای احاطه تمام رئوس این گراف کافی نیست.
ب) برای احاطه کردن رأس h حداقل یکی از رئوس e یا h باید در مجموعهٔ احاطهگر باشند و با بودن هر کدام از آنها در مجموعهٔ احاطهگر، رئوس g ،c ،b ،a کماکان احاطه نشده باقی میمانند.
پ) برای احاطه کردن رئوس g ،c ،b ،a حداقل دو رأس دیگر نیاز هست، زیرا هیچ رأسی بهتنهایی نمیتواند هر چهارتای آنها را احاطه کند.
ت) بنابراین حداقل 3 رأس باید در هر مجموعه احاطهگر از گراف G باشد یعنی $\gamma (G)\ge 3$.
ث) از طرفی چون $\left\{ a,c,e \right\}$ یک مجموعهٔ احاطهگر است، $\gamma (G)\le 3$. پس $\gamma (G)=3$.
2- میخواهیم عدد احاطهگر گراف شکل 13 را مشخص نماییم.
الف) ابتدا کران پایین $\left\lceil \frac{n}{\Delta +1} \right\rceil $ را بررسی میکنیم که عدد $ \left\lceil {\frac{{14}}{6}} \right\rceil = 3$ را میدهد. پس $\gamma (G)\ge 3$.
ب) اما حداقل یکی از رئوس d ،c ،b ، a باید انتخاب شود. چرا؟
پ) حداقل یکی از رئوس f و g باید انتخاب شود. چرا؟
ت) حداقل یکی از رئوس i و h باید انتخاب شود. چرا؟
ث) حداقل یکی از رئوس m و n باید انتخاب شود. چرا؟
ج) بنابراین حداقل 4 رأس در هر مجموعهٔ احاطهگر باید باشد. لذا $\gamma (G)\ge 4$ و با توجه به اینکه $\left\{ c,f,h,m \right\}$ یک مجموعهٔ احاطهگر است لذا $\gamma (G)\le 4$ بنابراین $\gamma (G)=4$
مثال: عدد احاطهگری گراف شکل 14 را بهدست آورید و یک مجموعهٔ احاطهگر مینیمم برای آن ارائه کنید.
حل: برای احاطه کردن رأس a لازم است یکی از دو رأس a و b در مجموعهٔ احاطهگر باشند. به همین صورت یکی از رئوس e و f و نیز یکی از رئوس i و j نیز باید در هر مجموعه احاطهگر باشند. اما این سه رأس انتخاب شده در هر حالت نمیتوانند رئوس l ،h ،d را احاطه کنند. لذا حداقل یک رأس دیگر یعنی حداقل 4 رأس برای احاطه رئوس این گراف لازم است: یعنی $\gamma (G)\ge 4$ از طرفی $\left\{ b,f,j,h \right\}$ یک مجموعهٔ احاطهگر است و لذا $\gamma (G)\le 4$.
بنابراین داریم $\gamma (G)=4$
تمرین (صفحهٔ 52 صفحهٔ کتاب درسی)
1- در مثال ایستگاههای رادیویی (دومین مثال این درس)
الف) تعداد و محل نصب ایستگاهها را مشخص نمایید.
ب) اگر مجبور باشیم یکی از ایستگاهها را در شهر b احداث کنیم حداقل چند ایستگاه دیگر و در چه شهرهایی باید احداث کنیم؟
2- نقشهٔ زیر نقشهٔ یک منطقه شامل چند روستا و جادههای بین آن روستاهاست و مسافت جادههای بین روستاها در آن مشخص شده است. قصد داریم چند بیمارستان مجهز در برخی روستاها احداث کنیم بهگونهای که فاصلهٔ هر روستا تا نزدیکترین بیمارستان به آن روستا از 10 کیلومتر بیشتر نباشد و از طرفی کمترین تعداد ممکن بیمارستان را احداث کنیم. ابتدا با توجه به نقشهٔ فوق، مسئلهٔ مورد نظر را با یک گراف مناسب مدلسازی کنید و سپس تعداد و محل احداث بیمارستانها را مشخص کنید.
3- عدد احاطهگری را برای هر یک از گرافهای زیر مشخص نمایید.
|
|
|
4- اگر برای گراف G داشته باشیم $\gamma (G)=1$، در اینصورت به چه ویژگیهایی از گراف G میتوان پی برد؟ $\Delta (G)$ و حداقل و حداکثر تعداد یالهایی را که گراف G میتواند داشته باشد مشخص کنید.)
5- $\gamma ({{P}_{n}})$ و $\gamma ({{C}_{n}})$ را بهازای هر $n\in \mathbb{N}$ مشخص کنید.
6- اگر G یک گراف $-k$ منتظم n رأسی باشد نشان دهید $\left\lceil \frac{n}{k+1} \right\rceil \le \gamma (G)$
7- یک گراف 2- منتظم 12 رأسی بکشید که عدد احاطهگری آن کمترین مقدار ممکن باشد.
8- الف) یک گراف 6 رأسی که $-\gamma $ مجموعهٔ آن با اندازه یک باشد رسم کنید.
ب) یک گراف 6 رأسی که $-\gamma $ مجموعهٔ آن با اندازه دو باشد رسم کنید.
پ) فرض کنید n و k دو عدد طبیعی باشند و $k\le \frac{n}{2}$. روشی برای رسم یک گراف n رأسی که عدد احاطهگری آن k باشد، ارائه دهید.
9- الف) یک گراف 6 رأسی با عدد احاطهگری 2 رسم کنید که یک مجموعهٔ احاطهگر یکتا با اندازهٔ 2 داشته باشد.
ب) یک گراف 6 رأسی با عدد احاطهگری 2 رسم کنید که بیش از یک مجموعهٔ احاطهگر با اندازهٔ 2 داشته باشد.
10- برای هر $(n\ge 4)n\in \mathbb{N}$ دلخواه توضیح دهید که
الف) چگونه میتوانید یک گراف n رأسی با عدد احاطهگری 2 رسم کنید که یک مجموعه احاطهگر یکتا با اندازهٔ 2 داشته باشد.
ب) چگونه میتوانید یک گراف n رأسی با عدد احاطهگری 2 رسم کنید که بیش از یک مجموعهٔ احاطهگر با اندازه 2 داشته باشد.
11- گراف ${{P}_{12}}$ رارسم کنید.
الف) یک $-\gamma $ مجموعه از آنرا مشخص نمایید.
ب) یک مجموعه احاطهگر مینیمال 6 عضوی از آنرا مشخص نمایید.